import java.io.*;
import java.util.*;

public class AlgorithmSolver
{
  public static final int WIDTH = 32+1;
  public static final int HEIGHT = 32+1;  
  public static final int numInPopulation = 100;
  public static final int maxInstructions = 20;
  public static final int minChanges = 1;
  public static final int totalNumEvolutionInstructionLists = 1010;
  public static final int MAX = 2000000000;
  public static final long longMAX = 2000000000000000l;
  public double speedWeight;
  ArrayList<ValueArray> data;
  ArrayList<Double> averages;
  ArrayList<Integer> mins;
  ArrayList<Integer> starts;
  ArrayList<ArrayList> previousPopulation;
  ArrayList<ArrayList> nextPopulation;
  public static final int numPopulations = 10;
   
  public AlgorithmSolver(double percentArrays)
  {
    System.out.println("Loading Data File.");
    data = loadData("data.txt",percentArrays);
	System.out.println("Calculating averages.");
	averages = new ArrayList<Double>();
	mins = new ArrayList<Integer>();
	starts = new ArrayList<Integer>();
	int actualMin = 0;
	for(int i = 0; i < data.size(); i++)
	{
	  ValueArray current = data.get(i);
	  double total = 0;
	  int min = MAX;
	  starts.add(new Integer(current.getValue(WIDTH/2,HEIGHT/2)));
	  for(int x = 0; x < WIDTH; x++)
	    for(int y = 0; y < HEIGHT; y++)
		{
		  total += current.getValue(x,y);
		  if(current.getValue(x,y) < min) min = current.getValue(x,y);
		}
	  mins.add(new Integer(min));
	  total = total / (WIDTH * HEIGHT);
	  actualMin += (int)(min * total);
	  averages.add(new Double(total));
	}
	System.out.println("Setting up initial algorithms.");
	previousPopulation = new ArrayList<ArrayList>();
	nextPopulation = new ArrayList<ArrayList>();
	previousPopulation.add(hexagonSearch(maxInstructions));
	previousPopulation.add(diamondSearch(maxInstructions));
	for( int i = 2; i < numPopulations; i++ ) previousPopulation.add(randomSearch(maxInstructions));
  }
  
  public void solve(int numIterations, int printInterval, int speedWeight)
  {
    printResultingInstructions();
    for(int a = 1; a < numIterations; a++)
    {
	    for(int i = 0; i < numPopulations; i++)
		{
		  ArrayList<ArrayList> nextInstructions = new ArrayList<ArrayList>();
		  for(int j = 0; j < numInPopulation; j++)
		  {
		    ArrayList<Instruction> newAlgorithm = generateNewAlgorithm(previousPopulation.get(i));
		    nextInstructions.add(newAlgorithm);
		  }
		  nextInstructions.add(previousPopulation.get(i));
		  nextPopulation.add(nextInstructions);
		}
		int absoluteMax = 0;
		//int z = 0;
		for(int i = 0; i < numPopulations; i++)
		{
			int[] results = new int[numInPopulation+1];
			ArrayList<ArrayList> nextInstructions = nextPopulation.get(i);
			//if(i==0) System.out.println(nextInstructions.get(13));
			for(int j = 0; j <= numInPopulation; j++)
			{
			  int total = 0;
			  ArrayList<Integer> speed = speedCost(nextInstructions.get(j));
			  //if(i ==0 & j == 13) System.out.println(speed);
			  for(int k = 0; k < data.size(); k++)
			  {
			    int[] output = interpret(nextInstructions.get(j),data.get(k),k);
				int best = output[0];
				int start = starts.get(k);
				int value = (start - best);
				
				value -= ( speedWeight * speed.get(output[1]) ) >> 7;
				value -= ( nextInstructions.get(j).size() ) >> 3;
				/*if(i==0 && j == 13 && (k%20==0)) 
				{
					System.out.print("Termination: " + output[1]);
					System.out.print(" Speed: " + speed.get(output[1]));
					System.out.print(" Score: " + (start-best));
					System.out.print(" Best: " + best);
					System.out.println(" Total: " + value);
					z+=value;
				}*/
				total += value;
			  }
			  results[j] = total;
			}
			int max = 0;
			int maxIndex = 0;
			for(int j = 0; j <= numInPopulation; j++)
			{
				if(results[j] > max)
				{
				  max = results[j];
				  maxIndex = j;
				}
			}
			previousPopulation.set(i,nextInstructions.get(maxIndex));
			results[maxIndex] = 0;
			if(max > absoluteMax) absoluteMax = max;
		}
		nextPopulation.clear();
		//System.out.println("Final Total:" + z);
		System.out.println("Iteration: " + a + " Best value so far: " + absoluteMax);
		if(a % printInterval == 0) printResultingInstructions();
	}
	printResultingInstructions();
  }
  
  public ArrayList<Integer> speedCost(ArrayList<Instruction> program)
  {
    ArrayList<Integer> speed = new ArrayList<Integer>();
	ListIterator iterator = program.listIterator();
	int numPreviousSADs = 0;
	int totalInstructions = 0;
	while(iterator.hasNext())
	{
	  Instruction current = (Instruction)iterator.next();
	  if(current.isQReset())
	  {
	    totalInstructions += 8;
	    if(numPreviousSADs != 0)
		{
		  totalInstructions += SADValue(numPreviousSADs);
		  numPreviousSADs = 0;
		}
	  }
	  else if(current.isReset())
	  {
	    if(numPreviousSADs != 0)
		{
		  totalInstructions += SADValue(numPreviousSADs);
		  numPreviousSADs = 0;
		}
		totalInstructions += 4;
	  }
	  else
	  {
		if(Math.abs(current.getX()) > 5 || Math.abs(current.getY()) > 5)
		{
		  totalInstructions += 4 + 100 + SADValue(numPreviousSADs);
		  numPreviousSADs = 0;
		}
		else numPreviousSADs++;
	  }
	  if(iterator.hasNext()) speed.add(totalInstructions);
	}
	if(numPreviousSADs != 0) totalInstructions += SADValue(numPreviousSADs);
	speed.add(totalInstructions);
	return speed;
  }
  
  public void printC(ArrayList<Instruction> algorithm)
  {
    System.out.println("omx = bmx;");
	System.out.println("omy = bmy;");
    LinkedList<Instruction> SADArray = new LinkedList<Instruction>();
    for(int i = 0; i < algorithm.size(); i++)
	{
	  Instruction instr = algorithm.get(i);
	  boolean skip = false;
	  if( (!instr.isSAD() && SADArray.size() != 0) || ( instr.isSAD() && (Math.abs(instr.getX()) > 5 || Math.abs(instr.getY()) > 5) ))
	  {
	    if( instr.isSAD() && (Math.abs(instr.getX()) > 5 || Math.abs(instr.getY()) > 5) )
		{
		  skip = true;
		}
	    if(SADArray.size() % 3 < SADArray.size() % 4)
	    {
		  int[][] coords = new int[3][2];
		  while(SADArray.size() >= 3)
		  {
			  for(int j = 0; j < 3; j++)
			  {
			    Instruction cur = SADArray.removeFirst();
			    coords[j][0] = cur.getX();
				coords[j][1] = cur.getY();
			  }
			  System.out.println("COST_MV_X3("+coords[0][0]+","+coords[0][1]+","+coords[1][0]+","+coords[1][1]+","+coords[2][0]+","+coords[2][1]+");");
		  }
		}
		else
		{
		  int[][] coords = new int[4][2];
		  while(SADArray.size() >= 4)
		  {
			  for(int j = 0; j < 4; j++)
			  {
			    Instruction cur = SADArray.removeFirst();
			    coords[j][0] = cur.getX();
				coords[j][1] = cur.getY();
			  }
			  System.out.println("COST_MV_X4("+coords[0][0]+","+coords[0][1]+","+coords[1][0]+","+coords[1][1]+","+coords[2][0]+","+coords[2][1]+","+coords[3][0]+","+coords[3][1]+");");
		  }
		}
		if(skip)
		{
		  SADArray.addLast(instr);
		}
		while(SADArray.size() > 0)
		{
		  Instruction cur = SADArray.removeFirst();
		  if(Math.abs(cur.getX()) > 5 || Math.abs(cur.getY()) > 5)
		  {
		    System.out.print("if(CHECK_MVRANGE(omx + "+cur.getX()+", omy + "+cur.getY()+")) ");
		  }
		  System.out.println("COST_MV(omx + "+cur.getX()+", omy + "+cur.getY()+");");
		}
	  }
	  if(instr.isReset())
	  {
		System.out.println("if(!CHECK_MVRANGE(bmx,bmy)) break;");
		System.out.println("omx = bmx;");
		System.out.println("omy = bmy;");
	  }
	  else if(instr.isQReset())
	  {
	    System.out.println("if((omx==bmx && omy == bmy) || !CHECK_MVRANGE(bmx,bmy)) break;");
		System.out.println("omx = bmx;");
		System.out.println("omy = bmy;");
	  }
	  else if(instr.isSAD() && !skip)
	  {
	    SADArray.addLast(instr);
	  }
	}
	System.out.println();
  }
  
  public void printResultingInstructions()
  {
    /*for(int i = 0; i < numPopulations; i++)
	{
	  for(int j = 0; j < previousPopulation.get(i).size(); j++)
	  {
		System.out.println(previousPopulation.get(i).get(j));
	  }
	  System.out.println();
	}*/
	System.out.println(previousPopulation.get(0));
	printC(previousPopulation.get(0));
  }
  
  public ArrayList<Instruction> generateNewAlgorithm(ArrayList<Instruction> algorithm)
  {
    ArrayList<Instruction> newAlgorithm = (ArrayList<Instruction>)algorithm.clone();
    Random generator = new Random();
	int numChanges = (int)(1.5 * Math.abs(generator.nextGaussian())) + minChanges;
	for(int i = 0; i < numChanges; i++) 
	{
	  int size = newAlgorithm.size();
	  int randomValue = generator.nextInt(8);
	  int curloc = generator.nextInt(size);
	  Instruction curinstr = newAlgorithm.get(curloc);
	  if(randomValue == 7 || randomValue == 6)
	  {
		swapInstructions(newAlgorithm,previousPopulation.get(generator.nextInt(numPopulations)));
	  }
	  else if(randomValue == 5)
	  {
	    newAlgorithm.remove(generator.nextInt(size));
	  }
	  else if(randomValue == 4)
	  {
	    newAlgorithm.add(generator.nextInt(size),Instruction.getRandomInstruction(0.2,4.0));
	  }
	  else if(randomValue == 3 && curinstr.isSAD())
	  {
		int newX = curinstr.getX() + (int)(generator.nextGaussian()*2);
		int newY = curinstr.getY() + (int)(generator.nextGaussian()*2);
	    Instruction newinstr = new Instruction(newX,newY);
		newAlgorithm.set(curloc,newinstr);
	  }
	  else if(randomValue == 2)
	  {
		newAlgorithm.add(curloc,new Instruction("QRESET"));
		for(int j = 0; j < generator.nextInt(6); j++) newAlgorithm.add(curloc,Instruction.getRandomInstruction(0,2.0));
	  }
	  else newAlgorithm.set(generator.nextInt(size),Instruction.getRandomInstruction(0.2,4.0));
	}
	return newAlgorithm;
  }
  
  public void swapInstructions (ArrayList<Instruction> newAlgorithm, ArrayList<Instruction> oldAlgorithm)
  {
    Random generator = new Random();
	int numInstructionsToRemove = generator.nextInt(5)+1;
	int numInstructionsToAdd = generator.nextInt(5)+1;
	if(numInstructionsToRemove >= newAlgorithm.size()) return;
	if(numInstructionsToAdd >= oldAlgorithm.size()) return;
	int oldAlgorithmIndex = generator.nextInt(oldAlgorithm.size()-numInstructionsToAdd);
	int newAlgorithmIndex = generator.nextInt(newAlgorithm.size()-numInstructionsToRemove);
	for(int i = 0; i < numInstructionsToRemove; i++)
		newAlgorithm.remove(newAlgorithmIndex);
	for(int i = 0; i < numInstructionsToAdd; i++)
		newAlgorithm.add(newAlgorithmIndex,oldAlgorithm.get(oldAlgorithmIndex+i));
  }
  
  public int[] interpret(ArrayList<Instruction> program, ValueArray array, int arrayLoc)
  {
    int curX = WIDTH/2;
	int curY = HEIGHT/2;
	int best = array.getValue(curX,curY);
	int bestX = curY;
	int bestY = curY;
	ListIterator iterator = program.listIterator();
	int i = -1;
	String string = "";
	while(iterator.hasNext())
	{
	  i++;
	  Instruction current = (Instruction)iterator.next();
	  if(current.isQReset())
	  {
	    if(curX == bestX && curY == bestY)
		  break;
		else
		{
		  curX = bestX;
		  curY = bestY;
		}
	  }
	  else if(current.isReset())
	  {
	    curX = bestX;
		curY = bestY;
	  }
	  else if(current.isSAD())
	  {
	    int newX = curX + current.getX();
		int newY = curY + current.getY();
		if(newX < 0 || newX >= WIDTH || newY < 0 || newY >= HEIGHT) {}
		else if(array.getValue(newX,newY) < best)
		{
		  best = array.getValue(newX,newY);
		  bestX = newX;
		  bestY = newY;
		}
	  }
	}
	//if(i == program.size()) i--;
	int[] result = new int[2];
	result[0] = best;
	result[1] = i;
	return result;
  }
  
  public int SADValue(int num)
  {
    int value = 0;
	if(num % 3 < num % 4)
	{
	  while(num >= 3)
	  {
	    value += 280;
	    num -= 3;
	  }
	}
	else
	{
	  while(num >= 4)
	  {
	    value += 370;
	    num -= 4;
	  }
	}
	value += num * 100;
	return value;
  }
  
  public ArrayList<Instruction> diamondSearch(int repeats)
  {
    ArrayList<Instruction> diamond = new ArrayList<Instruction>();
	for( int i = 0; i < repeats/5; i++ )
	{
	  diamond.add(new Instruction(0,1));
	  diamond.add(new Instruction(1,0));
	  diamond.add(new Instruction(-1,0));
	  diamond.add(new Instruction(0,-1));
	  diamond.add(new Instruction("QRESET"));
	}
	return diamond;
  }
  
  public ArrayList<Instruction> hexagonSearch(int repeats)
  {
    ArrayList<Instruction> hexagon = new ArrayList<Instruction>();
	for( int i = 0; i < repeats/5; i++ )
	{
	  hexagon.add(new Instruction(-2,0));
	  hexagon.add(new Instruction(2,0));
	  hexagon.add(new Instruction(-1,2));
	  hexagon.add(new Instruction(1,2));
	  hexagon.add(new Instruction(-1,-2));
	  hexagon.add(new Instruction(1,-2));
	  hexagon.add(new Instruction("QRESET"));
	}
	return hexagon;
  }
  
  public ArrayList<Instruction> randomSearch(int repeats)
  {
	ArrayList<Instruction> list = new ArrayList<Instruction>();
	for( int i = 0; i < repeats; i++ )
	{
	  list.add(Instruction.getRandomInstruction(0.1,4.0));
	}
	return list;
  }

  public ArrayList<ValueArray> loadData(String filename, double percentArrays)
  {
    ArrayList<ValueArray> data = new ArrayList<ValueArray>();
	String line = null;
	int valuesRead = 0;
	Random generator = new Random();
    try
    {
	  File f = new File(filename);
	  FileInputStream fis = new FileInputStream(f); 
	  BufferedInputStream bis = new BufferedInputStream(fis); 
	  DataInputStream dis = new DataInputStream(bis);
	  while ( (line = dis.readLine()) != null )
	  {
	    boolean skipArray = false;
	    ValueArray valueArray = new ValueArray(WIDTH,HEIGHT);
	    for( int h = 0; h < HEIGHT && (line = dis.readLine()) != null; h++ )
		{
		  StringTokenizer st = new StringTokenizer(line, ",");
		  for( int w = 0; w < WIDTH; w++ )
		  {
            if(!st.hasMoreTokens())
			{
			  skipArray = true;
			  break;
			}
		    String next = st.nextToken();
		    if(next == null) break;
		    int value = Integer.valueOf(next).intValue();
		    valueArray.setValue(w,h,value);
		  }
		}
		if(generator.nextDouble() > percentArrays) skipArray = true;
		if(!skipArray) 
		{
		  data.add(valueArray);
		  valuesRead++;
		  if(valuesRead % 1000 == 0) System.out.println(valuesRead + " arrays read.");
		}
	  }
	}
    catch (IOException e)
    {
      System.out.println("Exception: " + e);
      System.exit(0);
    }
	return data;
  }
}